1. Field of the Invention
The present invention relates to processing of a data stream in a communication system, and, more particularly, to interleaving data bits in segments of a data stream.
2. Description of the Related Art
Interleaving is a commonly employed technique for processing a data stream in communication systems. Interleaving generally comprises receiving N+1 data values (where N+1 is the length of the data stream segment and N is an integer greater than one), and rearranging the order of the N+1 values. Interleaving may be employed, for example, to remove non-random sequences of values in a data stream, or may be employed to reduce effects of burst errors inserted into the data as the segment of data passes through a transmission medium. Such rearranging of data values may be considered to be a mapping ƒ(*) as illustrated in FIG. 1. As shown in FIG. 1, an interleaver maps the address indices daddr (0) to daddr (3) of data values d(0)-d(3) in the segment to corresponding interleaved address indices addr (0) to addr (3) in the interleaved segment. A receiver reverses the interleaving of the data values by de-interleaving. The mapping may be of two forms. Either sequential data values are inserted into an interleaved output corresponding to the sequence of interleaved address indices (i.e., reading serial data into interleaved data in a buffer), or the sequence of interleaved address indices are used to access and output data values in corresponding memory addresses (i.e., reading serial data out of a buffer as interleaved data.
For example, FIG. 2 shows a method of generating a sequence of interleaved addresses from a counter for a mapping operation ƒ(*) specified for an interleaver operating in accordance with the CDMA 2000 standard of the prior art for turbo encoding of data segments. In accordance with the CDMA 2000 standard, the frame size (Nturbo+1) is the length of the segment of the data stream to be interleaved. The mapping operation ƒ(*) maps a linear sequence of data addresses {daddr(0), daddr(1), . . . , daddr(Nturbo)} of the segment into a permuted sequence of interleaved data addresses {addr(0), addr(1), . . . , addr(Nturbo)}.
At step 201, an (n+5)-bit counter is initialized to 0, where n is the smallest integer such than the frame size (Nturbo+1) is less than or equal to 2n+5. At step 202, then most significant bits (MSBs) are extracted from the output value of the counter and one is added to the value formed from the n MSBs. At step 203, the n least significant bits (LSBs) are retained from the result obtained in step 202. At step 204, the n-bit output value of a 32-entry look-up table (such as the table defined in the CDMA 2000 standard) is retrieved using the address formed from the 5 LSBs of the counter output of step 202. At step 205, the n-bit output value from the 32-entry look-up table obtained in step 204 is multiplied with the result of step 203, and the n LSBs are retained from the result.
At step 206, a tentative address is formed from the n LSBs obtained in step 205. The tentative address is formed by (a) bit-reversal of the 5 LSBs of the counter output to form the 5 MSBs of the tentative address, and (b) appending the results of step 205 as the n LSBs of the tentative address. At step 207, a test determines if the tentative output address value is less than or equal to Nturbo. If the tentative address value is less than or equal to Nturbo, then the address is accepted at step 208 as an interleaved data address of the interleaved segment. If the tentative address value is less than Nturbo, then the tentative address is discarded at step 209.
At step 210, a test determines if all interleaved data addresses addr(0), addr(1), . . . , addr(Nturbo) have been generated. If so, the mapping operation ends; otherwise, the counter is incremented at step 211, and the mapping operation returns to step 202 to generate the next address.
For an implementation of an interleaver using the mapping operation shown in FIG. 2, a multiplier is employed in step 205, and an extra iteration is required each time the tentative address formed at step 206 is not within the frame size.
In accordance with exemplary embodiments of the present invention, an interleaver includes a mapping operation that generates interleaved data addresses for a frame of data values without employing multiplication. In addition, embodiments of the present invention may generate valid interleaved data addresses for each iteration of the mapping operation.
An interleaver employing a mapping operating in accordance with the present invention generates an interleaved address for one sequence of data values by generating at least two counter values, each counter value having a predetermined offset from each other counter value. A bit-reversed value, an index value, and an accumulated value are retrieved for each of the counter values, wherein each of the bit-reversed, index, and accumulated values are identified by an address formed from a portion of the corresponding counter value. A tentative address is formed for each counter value from the corresponding bit-reversed, index, and accumulated values, and the one or more tentative addresses are compared with a threshold to generate a select value, the threshold based on the length of the sequence of data values. The interleaved address is then set as one of the tentative addresses based on the select value.
For further exemplary embodiments, a test determines whether an interleaved address is set for each of the sequence of data values, and, if not, each counter is incremented by a substantially equivalent increment value, the increment value determined by the counter value generating the tentative address set as the interleaved address. A new accumulated value is then set for the accumulated value identified by the portion of the corresponding counter value generating the tentative address set as the interleaved address, the new accumulated value representing one or more combinations of the index value identified by the corresponding portion of the counter value. An interleaver may repeat generating interleaved addresses until each of the sequence of data values is assigned to a corresponding interleaved address.